1. Field of the Invention
This invention relates to the field of Computer Aided Design (CAD) of integrated circuits. More specifically, the present invention concerns a timing-driven placement method utilizing an accurate and efficient interconnect timing model.
2. Description of the Related Art
Microelectronic integrated circuits comprise a large number of electronic components (cells) and associated interconnections which are fabricated on a silicon base or wafer (chip). The silicon base is typically contained in a package that has a number of contacts which provide external output and input connections for the components. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in various layers of a silicon chip.
The process of converting electrical circuit specifications into a layout is called the physical design. Physical design involves placing predefined cells and elements in a fixed area, and routing wires between them. The process can be tedious, time consuming, and prone to many errors due to tight tolerance requirements and the minuteness of individual components. Current technology allows fabrication of several million transistors of less than one micron in size on one chip, and future developments are expected to allow fabrication of substantially more components of even smaller size.
Due to the large number of components and the exacting requirements of the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time, and enhanced chip performance.
The ultimate goal of physical design is to determine an optimal arrangement of devices in a plane surface of a chip and to find an efficient interconnection or routing scheme between the devices to achieve the desired functionality. The arrangement of individual cells is known as a cell placement. Depending upon the input, placement methods are classified into two major groups, constructive placement and interactive improvement methods. The input to constructive placement methods comprises a set of blocks (containing one or more cells) along with a netlist; constructive placement methods provide locations for the blocks.
Iterative improvement methods, on the other hand, start with an initial placement, which is then modified in search of a better placement. Such methods are applied in a recursive or iterative manner until no further improvement is possible, or the solution is considered to satisfy some predetermined criteria. Further details regarding particular placement methods are provided in R. Scepanovic, J. Koford and A. Andreev, U.S. patent application Ser. No. 08/672,725, filed Jun. 28, 1996, now U.S. Pat. No. 5,831,863 incorporated by reference herein.
In general, placement methods function by generating large numbers of possible placements and comparing them in accordance with some criteria, which is typically referred to as fitness. The fitness of a placement can be measured in a number of different ways, for example, overall chip size. A small size is associated with high fitness and vice-versa. Another measure of fitness is total wire length; a high total indicates low fitness and vice-versa. The relative desirability of a placement can alternatively be expressed in terms of cost, which can be considered as the inverse of fitness, with high cost correpsonding to low fitness and vice-versa.
Traditionally, the prime objective of placement methods is to minimize the total layout area by carefully placing the given modules and making all required interconnections. The objective function of most conventional placement methods is set to minimize the total area and/or total net length as a metric to achieve the minimization of the layout area. These placement methods try to shorten the net lengths among modules by placing the modules with more net connections closer together. By minimizing the total wire length, the conventional placement methods also attempt to solve timing constraints, which are the focus of the present invention.
This conventional approach produces satisfactory performance as long as the delay attributable to interconnections is small compared with the delay of the cells. In the past, the difference between the estimated wire delay (in synthesis and placement) and the routed wire delay was relatively small because the total intrinsic cell delay was much larger than the total wire delay on each path. However, with advances in integrated circuit fabrication technology, the situation is changing dramatically. Namely, designers of deep submicron integrated circuits are discovering that, with device scaling, the influence of the interconnect delay is playing more significant role and that it cannot be neglected in the design process. Placement methods that minimize the total wire length may in some cases increase the interconnect delay at critical nets. One of the reasons is that the delays caused by the same length of the wire vary significantly for nets with different driving strengths and load characteristics. It is, therefore, necessary to use direct minimization of the interconnect delays if timing constraints are important.
In response to this problem, various prior art timing-driven placement methods have been developed to control the wire lengths on a set of critical paths. An additional term in the cost function is used to correct the placement in such a way to satisfy the time bounds for all signal paths through the circuit. These methods use a model which accounts for the interconnect by estimating parasitic capacitance (capacitance of the interconnect) using a half-perimeter bounding-box metric, and adding the parasitic capacitance to the total net input cell capacitance in order to obtain total driving cell load. An example is the method of W. Swartz and C. Sechen, “Timing Driven Placement for Large Standard Cell Circuits,” Proc. Design Automation Conference, June 1995, pp. 211-215, incorporated by reference herein. Path delay is then computed as a sum of all net delays for the path, and the delay of the net is determined as a sum of intrinsic delay of the gate plus the equivalent driver resistance multiplied with the total load seen by the driver. This model ignores interconnect resistance, which is not acceptable for deep submicron designs, especially those having half a million or more gates implemented using a 0.25 micron or 0.18 micron fabrication process.
In order to properly select an additional cost function term and optimize placement, conventional interconnect modeling schemes require significant improvement. It is no longer sufficient to model the interconnect delay as a linear function of the node capacitances (lumped capacitance model). The interconnect resistance should be taken into account and, to do that properly, the interconnect must be modeled as a network of distributed resistors and capacitors—an “RC tree.”
Prior art RC models are problematic. The danger of overly simplified prior art models based on wire length estimates for nets is that they may result in nonconvergence of the design process due to inconsistency of timing information at different levels of design. On the other hand, the most accurate prior art timing models, such as the Asymptotic Waveform Evaluation method (AWE), require post routing information and are computationally too expensive to be used (with routing estimates) in placement methods.
To summarize, the problem of obtaining consistent, accurate and efficient timing information for the timing-driven placement has not been satisfactorily solved by prior art methods, and involves two subproblems:                (a) unavailability of interconnect topology and exact wire lengths        (b) inappropriate interconnect models used in placement.        
What is needed is a method that utilizes all the information available at the placement level, and narrows the gap between net-oriented layout information and inherently path-oriented timing information. Bridging this gap is one of the most challenging obstacles to producing good timing-driven placement tools. Therefore, an object of the present invention is to provide a method that maximally utilizes all net information available during placement in order to obtain a timing estimate which is as realistic as is feasible at the placement level. Another object of the present invention is to provide a method with an interconnect delay model that is consistent with the timing models used at the design levels above placement (synthesis) and below placement (routing).